package greedy;

public class JiaYou {
//TODO:2023/8/20  下面是第一次 20号复习
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int sum = 0;
            int min = 0;
            for (int i = 0; i < gas.length; i++) {
                sum += (gas[i] - cost[i]);
                min = Math.min(sum, min);
            }

            if (sum < 0) return -1;
            if (min >= 0) return 0;

            for (int i = gas.length - 1; i > 0; i--) {
                min += (gas[i] - cost[i]);
                if (min >= 0) return i;
            }

            return -1;
        }


    public int canCompleteCircuit1(int[] gas, int[] cost) {
            int sum=0;
            int min=Integer.MAX_VALUE;
        for (int i = 0; i < gas.length; i++) {
            sum+=gas[i]-cost[i];
            min=Math.min(sum,min);
        }
        if (sum<0){
            return  -1;
        }
        if (min>0){
            return  0;
        }

        int cursum=0;
        for (int i = gas.length-1; i >=0 ; i--) {
            cursum+=gas[i]-cost[i];
            if (cursum+min>=0){
                return i;
            }
        }





            return  -1;



    }

    public static void main(String[] args) {

            int[]  gas={1,2,3,4,5};
            int[]  cost={3,4,5,1,2};
        JiaYou jiaYou = new JiaYou();
        System.out.println(jiaYou.canCompleteCircuit(gas, cost));
    }





}
